package code.classic150on2025;

import java.util.*;

/**
 * @author 26029
 * @date 2025/6/20
 * @description
 */
public class SlideWindow {
    // 209. 长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int len = nums.length;
        int nowSum = 0;
        int minLen = Integer.MAX_VALUE;
        while (right < len) {
            nowSum += nums[right];
            while (nowSum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                nowSum -= nums[left];
                left++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    // 3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int maxLen = 0;
        int left = 0, right = 0;
        boolean[] set = new boolean[256];
        while (right < len) {
            if (!set[s.charAt(right)]) {
                set[s.charAt(right)] = true;
                maxLen = Math.max(maxLen, right - left + 1);
            } else {
                while (s.charAt(left) != s.charAt(right)) {
                    set[s.charAt(left)] = false;
                    left++;
                }
                left++;
            }
            right++;
        }
        return maxLen;
    }

    // 30. 串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int sLen = s.length();
        int wLen = words[0].length();
        int wNum = words.length;
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // 外层循环 wLen 次
        for (int i = 0; i < wLen; i++) {
            // 每次循环，进行一次滑动窗口操作
            Map<String, Integer> mapi = new HashMap<>();
            int start = i, end = i;
            int hit = 0;
            while (end + wLen <= sLen) {
                String nowWord = s.substring(end, end + wLen);
                // 存在这个词
                if (map.containsKey(nowWord)) {
                    int num = mapi.getOrDefault(nowWord, 0) + 1;
                    mapi.put(nowWord, num);
                    hit++;
                    // 如果超了，start向右，一直到符合
                    while (mapi.get(nowWord) > map.get(nowWord)) {
                        String deleteWord = s.substring(start, start + wLen);
                        mapi.put(deleteWord, mapi.get(deleteWord) - 1);
                        start += wLen;
                        hit--;
                    }
                    // 如果匹配成功了
                    if (hit == wNum) {
                        list.add(start);
                        String deleteWord = s.substring(start, start + wLen);
                        mapi.put(deleteWord, mapi.get(deleteWord) - 1);
                        start += wLen;
                        hit--;
                    }
                }
                // 不存在这个词
                else {
                    start = end + wLen;
                    mapi.clear();
                    hit = 0;
                }
                end += wLen;
            }
        }
        return list;
    }

    // 76. 最小覆盖子串
    public String minWindow(String s, String t) {
        int minLen = Integer.MAX_VALUE;
        int minStartPos = 0;
        int sLen = s.length(), tLen = t.length();
        Map<Character, Integer> tmap = new HashMap<>();
        for (int i = 0; i < tLen; i++) {
            tmap.put(t.charAt(i), tmap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0;
        int hit = 0;
        Map<Character, Integer> smap = new HashMap<>();
        while (right < sLen) {
            char now = s.charAt(right);
            if (tmap.containsKey(now)) {
                smap.put(now, smap.getOrDefault(now, 0) + 1);
                if (Objects.equals(smap.get(now), tmap.get(now))) {
                    hit++;
                }
                while (hit == tmap.size()) {
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        minStartPos = left;
                    }
                    char leftChar = s.charAt(left);
                    if (tmap.containsKey(leftChar)) {
                        smap.put(leftChar, smap.get(leftChar) - 1);
                        if (smap.get(leftChar) < tmap.get(leftChar))
                            hit--;
                    }
                    left++;
                }
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStartPos, minStartPos + minLen);
    }
}
